import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum2 {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        process(false, candidates, 0, target);
        return ans;
    }

    public void process(boolean flag, int[] nums, int i, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }
        if (i == nums.length) return;

        process(false, nums, i + 1, target);
        if (target - nums[i] >= 0 && !(i > 0 && nums[i] == nums[i - 1] && !flag)) {
            list.add(nums[i]);
            process(true, nums, i + 1, target - nums[i]);
            list.remove(list.size() - 1);
        }
    }
}
